contents

크루스칼 알고리즘은 가중치가 있는 무방향 연결 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST) 를 찾는 알고리즘입니다. MST는 모든 정점을 사이클 없이 연결하면서 간선 가중치의 합이 최소가 되는 간선들의 부분 집합입니다.

이 알고리즘은 간선에 초점을 맞춘 탐욕 알고리즘(greedy algorithm) 입니다. 모든 간선을 가중치 순으로 정렬한 다음, 사이클을 만들지 않는 가장 비용이 적게 드는 간선부터 차례대로 추가하여 모든 정점이 연결될 때까지 반복합니다.

핵심 아이디어 💡

크루스칼 알고리즘은 처음에 분리된 트리들의 "숲"을 만들고, 이 트리들이 결국 하나의 트리로 합쳐지도록 MST를 구축합니다. 항상 전역적으로 가장 비용이 적은 간선을 고려하며, 그 간선이 이전에 연결되지 않았던 두 개의 컴포넌트(트리)를 연결하는 경우에만 성장하는 숲에 추가합니다.

비유: 여러 개의 섬(정점)과 그 사이에 건설 비용이 다른 잠재적인 다리(간선)들이 있다고 상상해 보세요. 최소의 총 다리 건설 비용으로 모든 섬을 연결하고 싶습니다. 크루스칼 알고리즘은 가능한 모든 다리 목록을 비용 순으로 정렬한 다음, 가장 저렴한 다리부터 건설하고, 그다음 저렴한 다리를 건설하는 방식과 같습니다. 단, 이미 건설된 다리들을 통해 (직간접적으로) 연결된 두 섬을 연결하는 다리는 중복(사이클)이 되므로 건너뜁니다.

알고리즘 단계 🚶‍♂️

1. 초기화:
   • 그래프의 모든 간선 목록을 만듭니다.
   • 이 간선 목록을 가중치의 비내림차순(오름차순)으로 정렬합니다.
   • 서로소 집합 자료구조(Disjoint Set Union, DSU) (Union-Find라고도 함)를 생성합니다. 각 정점이 자신만의 별도 집합(컴포넌트)에 속하도록 초기화합니다.
   • 결과 MST의 간선들을 저장할 빈 목록을 초기화합니다.
   • MST에 추가된 간선의 수를 0으로 초기화합니다.
2. 반복: 정렬된 간선 목록을 순회합니다.
   • 현재 간선 (u, v) (가중치 w)에 대해:
     • 사이클 확인: DSU 구조를 사용하여 정점 u와 v가 이미 같은 집합에 속하는지 확인합니다(즉, find(u) == find(v)).
     • 사이클이 없다면: 만약 u와 v가 다른 집합에 있다면, 이 간선을 추가해도 사이클이 생성되지 않습니다.
       • 간선 (u, v)를 MST 목록에 추가합니다.
       • DSU의 union(u, v) 연산을 사용하여 u와 v를 포함하는 집합을 합칩니다.
       • 간선 카운터를 증가시킵니다.
     • 사이클이 있다면: 만약 u와 v가 이미 같은 집합에 있다면, 이 간선을 추가하면 사이클이 생성됩니다. 이 간선은 건너뛰고 다음 간선으로 넘어갑니다.
3. 종료: MST 목록에 V-1개의 간선이 추가되거나(여기서 V는 정점의 수), 모든 간선을 처리하면 중단합니다. 추가된 간선들의 목록이 MST를 형성합니다.

핵심 자료구조: 서로소 집합 자료구조 (DSU)

크루스칼 알고리즘의 효율성은 다음 두 가지 연산을 빠르게 수행하는 DSU 자료구조에 크게 의존합니다.

• find(i): 원소 i가 속한 집합을 결정합니다. 두 정점이 이미 연결되어 있는지 확인하는 데 사용됩니다.
• union(i, j): 원소 i와 j를 포함하는 집합을 합칩니다. 이전에 분리된 두 컴포넌트를 연결하는 간선을 추가할 때 사용됩니다.

경로 압축(path compression) 및 랭크/크기 기반 합집합(union by rank/size) 최적화를 사용하면, DSU 연산은 평균적으로 거의 상수 시간에 가깝게 걸립니다(상각된 O(α(V)), 여기서 α는 매우 느리게 증가하는 역 아커만 함수).

시간 복잡도

1. 간선 정렬: O(E log E), 여기서 E는 간선의 수입니다.
2. DSU 초기화: O(V), 여기서 V는 정점의 수입니다.
3. 간선 순회: 모든 E개의 간선을 순회합니다. 각 간선에 대해 두 번의 find 연산과 잠재적으로 한 번의 union 연산을 수행합니다. 최적화된 DSU를 사용하면 이 부분은 대략 O(E α(V)) 시간이 걸립니다.

일반적으로 가장 큰 비중을 차지하는 것은 간선 정렬입니다. 따라서 크루스칼 알고리즘의 전체 시간 복잡도는 일반적으로 O(E log E) 또는 O(E log V) 입니다 (밀집 그래프에서는 E가 V²에 가까울 수 있으므로 log E는 최대 2 log V가 될 수 있음).

크루스칼 알고리즘 vs. 프림 알고리즘

둘 다 MST를 찾지만, 접근 방식이 다릅니다.

references